package _14_btree;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/17 - 0:51
 * B树定义，这里省略了 value 值
 */
public class BTree {

    static class Node {
        int[] keys; // 关键字
        Node[] children; // 孩子
        int keyNumber; // 有效关键字个数
        boolean leaf = true; // 是否叶子节点
        int t; // 最小度数（最少孩子树）>=2  最多孩子树=2t

        Node(int t) {
            this.t = t;
            this.children = new Node[2 * t];
            this.keys = new int[2 * t - 1];
        }

        public Node(int[] keys) {
            this.keys = keys;
        }

        // 多路查找
        Node get(int k) {
            int i = 0;
            for (; i < keyNumber; i++) {
                if (k == keys[i]) {
                    return this;
                }
                if (k < keys[i]) { // 小于表示要到子节点中找，当前节点的所有key已经不满足了
                    break;
                }
            }
            if (leaf) {
                // 当前已经是叶子节点了还没找到
                return null;
            }
            // 走到这里表示有两种情况，1是k<keys[i]，2是i==keyNumber
            // 非叶子节点情况
            return children[i].get(k);
        }

        // 向 keys 中添加新key
        void insertKey(int index, int k) {
            System.arraycopy(keys, index, keys, index + 1, keyNumber - index);
            keys[index] = k;
            keyNumber++;
        }

        // 向指定下标处插入新的孩子
        void insertChild(int index, Node node) {
            System.arraycopy(children, index, children, index + 1, keyNumber - index);
            children[index] = node;
        }

        // 移除keys下标i处的元素
        int removeKey(int i) { // 1,2,3,4
            int k = keys[i];
            System.arraycopy(keys, i + 1, keys, i, --keyNumber - i);
            return k;
        }

        // 移除最左边的 key
        int removeLeftMostKey() {
            return removeKey(0);
        }

        // 移除最右边的 key
        int removeRightMostKey() {
            return removeKey(keyNumber - 1);
        }

        // 移除第i下标处的孩子
        Node removeChild(int i) {
            Node c = children[i];
            System.arraycopy(children, i + 1, children, i, keyNumber - i);
            children[keyNumber] = null;
            return c;
        }

        // 移除最左边的 child
        Node removeLeftMostChild() {
            return removeChild(0);
        }

        // 移除最右边的 child
        Node removeRightMostChild() {
            return removeChild(keyNumber);
        }

        // children[i[处左边的元素
        Node childLeftSibling(int i) {
            return i > 0 ? children[i - 1] : null;
        }

        // children[i]处左边的元素
        Node childRightSibling(int i) {
            return i != keyNumber ? children[i + 1] : null;
        }

        // 复制当前节点的所有keys和child到target中
        private void move2Target(Node target) {
            if (!leaf) {
                for (int i = 0; i <= keyNumber; i++) {
                    // 调用此方法前，target总是会先收到父节点分裂的key，所以keys数量会多出1，因而这里target.keyNumber不用再+1
                    target.children[target.keyNumber + i] = children[i];
                }
            }
            for (int i = 0; i < keyNumber; i++) {
                target.keys[target.keyNumber++] = keys[i];
            }
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(keys, 0, keyNumber));
        }
    }

    Node root;
    final int t; // 树中节点的最小度数
    final int MIN_KEY_MUNBER; // keys 最小个数
    final int MAX_KEY_MUNBER; // keys 最大个数

    public BTree(int t) {
        if (t < 2) {
            t = 2;
        }
        this.t = t;
        root = new Node(t);
        MIN_KEY_MUNBER = t - 1;
        MAX_KEY_MUNBER = 2 * t - 1;
    }

    public BTree() {
        this(2);
    }

    /**
     * 删除
     */
    public void remove(int key) {
        remove(null, root, 0, key);
    }

    /**
     * 删除的6种情况(删除后当前节点的key小于最小key值才会调整平衡，否则正常删除)：
     * case1：当前节点是叶子节点，没找到  => 结束
     * case2：当前节点是叶子节点，找到了  => 直接删除即可
     * case3：当前节点是非叶子节点，没找到  => 递归，在孩子中继续查找
     * case4：当前节点是非叶子节点，找到了  => 找后继，让后继代替当前节点删除
     * case5：删的不是根，并且key数目小于了下限(不平衡了)，又分以下几种情况
     *      case5-1：看看左兄弟是否富裕(左兄弟的keys大于t-1表示富裕) => 右旋，父节点前驱key下来给当前节点，左兄弟上去一个最大的key，如果左兄弟不是叶子节点，还要将左兄弟最后一个孩子作为第一个孩子给当前节点
     *      case5-2：没有左兄弟或左兄弟不富裕，看看右兄弟，右兄弟富裕 => 左旋，父节点下来一个，右兄弟上去一个key
     *      case5-3：左右兄弟都穷，向左兄弟那合并 (也可以向右合并)
     *          case5-3-1：有左兄弟：当前节点先移除，父节点的keys下移给左兄弟的右侧，然后当前节点keys再全部给左兄弟的右侧，递归处理父节点
     *          case5-3-2：没有左兄弟，右兄弟移除，父节点的keys下移给当前的右侧，然后右兄弟keys再全部给当前的右侧，递归处理父节点
     * case6：根节点  => 根节点没有key，但是它的孩子有key => 孩子替换掉根
     *
     * @param parent 调整节点的父节点
     * @param n 调整节点
     * @param index 调整节点是父节点的第几个孩子
     * @param key 查找key
     */
    private void remove(Node parent, Node n, int index, int key) {
        int i = 0;
        for (; i < n.keyNumber; i++) {
            if(key <= n.keys[i]) {
                break;
            }
        }
        /*
            n节点中找到了，删除第i个key
            n节点中没找到，继续找第i个孩子
         */

        if(n.leaf) {
            if(!found(n, key, i)) {
                // case1
                return;
            } else {
                // case2
                n.removeKey(i);
            }
        } else {
            if(!found(n, key, i)) {
                // case3
                remove(n, n.children[i], i, key);
            } else {
                // case4
                /*
                    找后继，让后继替死
                 */
                Node s = n.children[i + 1];
                while (!s.leaf) {
                    s = s.children[0];
                }
                n.keys[i] = s.keys[0];
//                remove(s, s.keys[0]);
                remove(n, n.children[i + 1], i + 1, s.keys[0]);
            }
        }

        // 验证是否失衡
        if(n.keyNumber < MIN_KEY_MUNBER) {
            // case5 case6
            balance(parent, n, index);
        }
    }

    /**
     * 调整失衡
     * @param parent 父节点
     * @param n 调整节点
     * @param i 调整节点在父节点children的下标
     */
    private void balance(Node parent, Node n, int i) {
        if(n == root) {
            // case6 根节点
            if(n.keyNumber == 0 && n.children[0] != null) {
                // 根节点最少有2个孩子，除非根节点也是叶子，否则该树不平衡
                root = root.children[0];
            }
            return;
        }

        Node left = parent.childLeftSibling(i); // 左兄弟
        Node right = parent.childRightSibling(i); // 右兄弟

        if(left != null && left.keyNumber > MIN_KEY_MUNBER) {
            // case5-1 左边富裕 右旋
            // a) 父节点的前驱key作为当前节点的第0个key
            n.insertKey(0, parent.keys[i - 1]);
            if(!left.leaf) {
                // b) 左边最右的孩子作为当前节点的第一个孩子
                n.insertChild(0, left.removeRightMostChild());
            }
            // c) 左边最大的key给父节点
            parent.keys[i - 1] = left.removeRightMostKey();
            return;
        }
        if(right != null && right.keyNumber > MIN_KEY_MUNBER) {
            // case5-2 右边富裕 左旋
            n.insertKey(n.keyNumber, parent.keys[i]);
            if(!right.leaf) {
                n.insertChild(n.keyNumber + 1, right.removeLeftMostChild());
            }
            parent.keys[i] = right.removeLeftMostKey();
            return;
        }

        // case5-3 两边都不富裕，向左合并
        if(left != null) {
            // a) case5-3-1 有左兄弟，当前节点向左兄弟合并，先断开当前节点
            parent.removeChild(i);
            // b) 父节点向下合并
            left.insertKey(left.keyNumber, parent.removeKey(i - 1));
            // c) 当前节点key向左兄弟合并
            n.move2Target(left);
        } else {
            // case5-3-2 右兄弟向当前节点合并
            parent.removeChild(i + 1);
            n.insertKey(n.keyNumber, parent.removeKey(i));
            right.move2Target(n);
        }
    }

    private boolean found(Node n, int key, int i) {
        return i < n.keyNumber && key == n.keys[i];
    }

    /**
     * 新增
     *
     * @param key
     */
    public void put(int key) {
        put(root, key, null, 0);
    }

    /**
     * 递归查找，并添加
     *
     * @param node   当前递归到的节点
     * @param key
     * @param parent 当前节点的父亲
     * @param index  当前节点在父亲 children 中的下标
     */
    private void put(Node node, int key, Node parent, int index) {
        int i = 0;
        for (; i < node.keyNumber; i++) {
            if (key == node.keys[i]) {
                // 更新操作
                return;
            }
            if (key < node.keys[i]) {
                break;
            }
        }

        if (node.leaf) {
            // 如果当前节点是叶子则直接插入 key
            node.insertKey(i, key);
        } else {
            // 递归找孩子
            put(node.children[i], key, node, i);
        }

        // 如果节点 keys 已满，则分裂，右侧孩子生成一个新节点做为父亲的孩子，中间的给父亲，左侧孩子不变
        if (node.keyNumber == MAX_KEY_MUNBER) {
            // 级联分裂
            split(node, parent, index);
        }
    }

    /**
     * 分裂节点，参照图片 img/叶子节点分裂.png
     *
     * @param left   被分裂的节点
     * @param parent 被分裂的父节点
     * @param index  被分裂节点在父节点 children  的下标位置
     */
    public void split(Node left, Node parent, int index) {
        /*            t=2，右节点需要分裂

                    3                                 3|5
                  /  \            ==>                / | \
                1|2  4|5|6                        1|2  4  6

         */
        if (root == left) {
            // 如果是根节点分裂
            root = new Node(t);
            root.leaf = false;
            root.insertChild(0, left);
            parent = root;
        }
        // 创建右侧节点
        Node right = new Node(t);
        // 新节点和右节点的 leaf 相同
        right.leaf = left.leaf;
        // 复制 t - 1 个元素到 right
        System.arraycopy(left.keys, t,
                right.keys, 0, t - 1);
        if (!left.leaf) {
            // left 如果是非叶子节点还需拷贝t个孩子到 right 中
            System.arraycopy(left.children, t, right.children, 0, t);
        }
        right.keyNumber = t - 1;
        left.keyNumber = t - 1;

        // 分裂一些到父节点中
        int mid = left.keys[t - 1];
        parent.insertKey(index, mid);
        // 新节点 right 作为父节点的孩子
        parent.insertChild(index + 1, right);
    }

    /**
     * key 是否存在
     */
    public boolean contains(int key) {
        return root.get(key) != null;
    }

    @Override
    public String toString() {
        if (root == null) {
            return "Empty tree";
        }

        StringBuilder sb = new StringBuilder();
        toString(root, sb, 0);
        return sb.toString();
    }

    private void toString(Node node, StringBuilder sb, int level) {
        sb.append(getIndent(level));
        sb.append(node.toString());
        sb.append("\n");

        if (!node.leaf) {
            for (int i = 0; i < node.keyNumber + 1; i++) {
                if (node.children[i] != null) {
                    toString(node.children[i], sb, level + 1);
                }
            }
        }
    }

    private String getIndent(int level) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < level; i++) {
            sb.append("    |--");
        }
        if (level > 0) {
            sb.append(" ");
        }
        return sb.toString();
    }

    public void travel() {
        doTravel(root);
    }

    public void doTravel(Node node) {
        if (node == null) {
            return;
        }
        int i = 0;
        for (; i < node.keyNumber; i++) {
            doTravel(node.children[i]);
            System.out.println(node.keys[i]);
        }
        doTravel(node.children[i]);
    }
}
